package Test;

import sun.security.x509.RFC822Name;

import javax.swing.*;
import javax.swing.tree.TreeNode;
import java.util.*;

class Solution {
    class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        public TreeNode() {

        }
        public TreeNode(int val) {
            this.val = val;
        }
    }
    public List<List<Integer>> levelOrder(TreeNode root) {
        if(root == null) {
            return null;
        }
        List<List<Integer>> ret = new ArrayList<>();
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while(!queue.isEmpty()) {
            List<Integer> list = new LinkedList<>();
            int size = queue.size();
            while(size != 0) {
                TreeNode tmp = queue.poll();
                list.add(tmp.val);
                ret.add(list);
                if(tmp.left != null) {
                    queue.offer(tmp.left);//tmp.left可能为空，不能offer空
                }
                if(tmp.right != null) {
                    queue.offer(tmp.right);

                }
                size--;
            }
        }
        return ret;
    }

    public static void main(String[] args) {
        Deque<Integer> queue = new LinkedList<>();
        Queue<Integer> queue2 = new ArrayDeque<>();
        queue.offer(null);
    }
}

class lowestCommonAncestor {
    static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        public TreeNode() {

        }
        public TreeNode(int val) {
            this.val = val;
        }
    }


    private boolean getPath(TreeNode root,TreeNode node,Stack<TreeNode> stack) {
        if(root == null) {
            return false;
        }
        stack.push(root);
        if(root == node) {
            return true;
        }
        boolean flgLeft = getPath(root.left,node,stack);
        if(flgLeft) {
            return true;
        }
        boolean flgRight = getPath(root.right,node,stack);
        if(flgRight) {
            return true;
        }
        stack.pop();
        return false;
    }

    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if(root == null) {
            return null;
        }
        Stack<TreeNode> stackP = new Stack<>();
        Stack<TreeNode> stackQ = new Stack<>();
        getPath(root,p,stackP);
        getPath(root,q,stackQ);
        int sizeP = stackP.size();
        int sizeQ = stackQ.size();
        int size = sizeP - sizeQ;
        if(size > 0) {
            while(size != 0) {
                stackP.pop();
                size--;
            }
        }else {
            size = -size;
            while(size != 0) {
                stackQ.pop();
                size--;
            }
        }
        while(!stackP.isEmpty()) {
            if(stackP.peek() == stackQ.peek()) {
                return stackP.peek();
            }
            stackP.pop();
            stackQ.pop();
        }
        return null;
    }

    public String tree2str(TreeNode root) {
        StringBuilder stringBuilder = new StringBuilder();
        test2strChirld(root,stringBuilder);
        return stringBuilder.toString();
    }
    public void test2strChirld(TreeNode t,StringBuilder stringBuilder) {
        if(t == null) {
            return;
        }
        stringBuilder.append(t.val);
        if(t.left != null) {
            stringBuilder.append("(");
            test2strChirld(t.left,stringBuilder);
            stringBuilder.append(")");
        }else {
            if(t.right != null) {
                stringBuilder.append("()");
            }else {
                return;
            }
        }
        if(t.right != null) {
            stringBuilder.append("(");
            test2strChirld(t.right,stringBuilder);
            stringBuilder.append(")");
        }else {
            return;
        }
    }

    public static void main(String[] args) {
        TreeNode one = new TreeNode(1);
        TreeNode two = new TreeNode(2);
        TreeNode three = new TreeNode(3);
        one.left = null;
        one.right = two;
        two.left = three;
        two.right = null;
        three.left = null;
        three.right = null;
        System.out.println(postorderTraversal(one));

    }
    public static List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> ret = new LinkedList<>();
        if(root == null) {
            return ret;
        }
        Stack<TreeNode> stack = new Stack<>();
        TreeNode cur = root;
        while(cur != null || !stack.isEmpty()) {
            while (cur != null) {
                stack.push(cur);
                cur = cur.left;
            }
            //栈里面最上面的的节点左边为空
            TreeNode up = stack.peek();
            if (up.right == null) {
                ret.add(stack.pop().val);
            }else {
                cur = up.right;
                up.right = null;
            }
        }
        return ret;
    }

    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> ret = new LinkedList<>();
        Stack<TreeNode> stack = new Stack<>();
        if(root == null) {
            return ret;
        }
        TreeNode cur = root;
        while(cur != null || !stack.isEmpty()) {
            while (cur != null) {
                ret.add(cur.val);
                stack.push(cur);
                cur = cur.left;
            }
            TreeNode up = stack.pop();
            cur = up.right;
        }
        return ret;
    }

    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> ret = new LinkedList<>();
        if(root == null) {
            return ret;
        }
        Stack<TreeNode> stack = new Stack<>();
        TreeNode cur = root;
        while(cur != null || !stack.isEmpty()) {
            while (cur != null) {
                stack.push(cur);
                cur = cur.left;
            }
            TreeNode up = stack.pop();
            ret.add(up.val);
            if (up.right != null) {
                cur = up.right;
            }
        }
        return ret;
    }

    public List<List<Integer>> levelOrderBottom(TreeNode root) {
        List<List<Integer>> ret = new ArrayList<>();
        if(root == null) {
            return ret;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while(!queue.isEmpty()) {
            int size = queue.size();
            List<Integer> cen = new LinkedList<>();
            while(size != 0) {
                TreeNode tmp = queue.poll();
                cen.add(tmp.val);
                size--;
                if(tmp.left != null) {
                    queue.offer(tmp.left);
                }
                if(tmp.right != null) {
                    queue.offer(tmp.right);
                }
            }
            ret.add(cen);
        }
        Collections.reverse(ret);
        return ret;
    }



    public List<List<Integer>> levelOrder(TreeNode root) {
        // 每层节点保存到一个list中
        List<List<Integer>> ret = new ArrayList<>();
        if(null == root)
            return ret;
        Queue<TreeNode> q = new LinkedList<>();
        q.offer(root);
        while(!q.isEmpty()){
            // 遍历当前层中的所有节点，讲下一层的节点入栈
            int size = q.size();   // 本层中的所有节点
            List<Integer> level = new ArrayList<>(size);
            for(int i = 0; i < size; ++i){
                TreeNode cur = q.poll();
                level.add(cur.val);
                // 如果cur的左子树不为空，将左子树入队列
                if(null != cur.left){
                    q.offer(cur.left);
                }
                // 如果cur的右子树不为空，将右子树入队列
                if(null != cur.right){
                    q.offer(cur.right);
                }
            }
            // 本层节点已经遍历完毕，并且下一层的节点已经保存到队列中
            ret.add(level);
        }
        return ret;
    }
}



/*
解题思路：二叉树层序遍历的变形
1. 如果是空树直接返回
2. 层序遍历需要用到队列，定义一个队列，里面放置节点的地址，将根节点如队列
3. 队列非空时，循环进行一下操作：
    a. 队列中当前元素都是在同一层的，依次取出遍历，保存到同一个vector中
        取到一个节点时候：
           >> 保存该节点
           >> 如果该节点左子树存在，将该左子树入队列
           >> 如果该节点右子树存在，将该节点右子树入队列
           >> 将当前已遍历节点从队列中拿出来
     b. 本层节点遍历结束后，保存到返回的vector中，此时下一层节点已经全部入队列
*/